alpha–beta pruning

Alpha–beta pruning is a variant of minimax search for zero-sum two player games. It adopts a similar insight to branch and bound for simple tree search. As there are two players, it keeps a 'best so far' value for each player. By convention alpha is the best for the first player and beta for the second, but these swop as one moves down the game tree alternating the players' turns.

Imagine the first player has examined a numer of possible moves and has a 'best so far' move with score 10. It starts to explore a new move M and looks at the second player's options. As soon as it encounters a move with the second player's score greater than -10 (so first player worse than 10), it can prune the whole of the branch associated with M as it is clearly less good than the 'best so far' move. A similar strategy is used recursively but alternating 'best so far' roles. Note, like minimax, alpha–beta pruning assumes a perfect opponent.